

def dp(状态1，状态2，...)
	for 选择 in 所有可能的选择
	# 此时的状态因为已经做了选择而改变
	result = 求最值(result, dp(状态1，状态2，...))

return result

class Solution {
public:
    int fib(int n) 
    {
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;

        return fib(n - 1) + fib(n - 2);
    }
};


class Solution {
public:
    // int fib(int n) 
    // {
    //     if(n == 0)
    //         return 0;
    //     if(n == 1)
    //         return 1;

    //     return fib(n - 1) + fib(n - 2);
    // }

    // int fib(int n)
    // {
    //     int memo[n + 1]; // 定义一个备忘录，减少冗余计算
    //     memset(memo, 0, sizeof(memo)); // 初始化全为0

    //     // 进行带备忘录的递归
    //     return dp(memo, n);
    // }

    // int dp(int* memo, int n)
    // {
    //     if(n == 0 || n == 1)
    //         return n;

    //     if(memo[n] != 0) // 已经计算过了，不用再计算了
    //         return memo[n];

    //     memo[n] = dp(memo, n - 1) + dp(memo, n - 2);

    //     return memo[n];
    // }

    int fib(int n)
    {
        // 建立一个备忘录，并初始化为0
        int memo[n + 1];
        memset(memo, 0, sizeof memo);

        return dp(memo, n);
    }

    int dp(int* memo, int n)
    {
        if(n == 0 || n == 1)
            return n;

        if(memo[n] != 0) // 如果已经计算过了，直接返回备忘录中记录的值即可
            return memo[n];

        memo[n] = dp(memo, n - 1) + dp(memo, n - 2);

        return memo[n];
    }
};


class Solution {
public:
    int climbStairs(int n) 
    {
        // 建立一个备忘录，并全部初始化成0
        int memo[n + 1];
        memset(memo, 0, sizeof memo);

        return dp(memo, n);
    }

    int dp(int* memo, int n)
    {
        if(n == 1 || n == 2)
            return n;

        if(memo[n] != 0)
            return memo[n];

        memo[n] = dp(memo, n - 1) + dp(memo, n - 2);

        return memo[n];
    }
};


class Solution {
public:
    int fib(int n) 
    {
        if(n == 0 || n == 1)
            return n;

        vector<int> dp(n + 1, 0);

        dp[0] = 0;
        dp[1] = 1;

        for(int i = 2; i < n + 1; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
            dp[i] = dp[i] % 1000000007;
        }

        return dp[n];
    }
};


class Solution {
public:
    // int fib(int n) 
    // {
    //     if(n == 0 || n == 1)
    //         return n;

    //     vector<int> dp(n + 1, 0);

    //     dp[0] = 0;
    //     dp[1] = 1;

    //     for(int i = 2; i < n + 1; i++)
    //     {
    //         dp[i] = dp[i - 1] + dp[i - 2];
    //         dp[i] = dp[i] % 1000000007;
    //     }

    //     return dp[n];
    // }

    int fib(int n)
    {
        vector<int> memo(n + 1, 0);

        return dp(memo, n);
    }

    int dp(vector<int>& memo, int n)
    {
        if(n == 0 || n == 1)
            return n;

        if(memo[n] != 0)
            return memo[n];

        memo[n] = dp(memo, n - 1) + dp(memo, n - 2);

        memo[n] %= 1000000007;

        return memo[n];
    }
};



class Solution {
public:
    // int numWays(int n) 
    // {
    //     // 带备忘录的递归解法
    //     vector<int> memo(n + 1, 0);

    //     return dp(memo, n);
    // }

    // int dp(vector<int>& memo, int n)
    // {
    //     if(n == 0)
    //         return 1;

    //     if(n == 1 || n == 2)
    //         return n;
        
    //     if(memo[n] != 0)
    //         return memo[n];

    //     memo[n] = dp(memo, n - 1) + dp(memo, n - 2);

    //     memo[n] %= 1000000007;

    //     return memo[n];
    // }

    int numWays(int n)
    {
        // 迭代递推解法
        vector<int> dp(n + 1, 0);

        if(n == 0)
            return 1;
        if(n == 1 || n == 2)
            return n;

        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;

        for(int i = 3; i < n + 1; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
            dp[i] %= 1000000007;
        }

        return dp[n];
    }
};


class Solution {
public:

    vector<int> memo; // 定义备忘录

    int coinChange(vector<int>& coins, int amount) 
    {
        memo.resize(amount + 1);
        fill(memo.begin(), memo.end(), -666);

        return dp(coins, amount);
    }

    // 状态：原问题和子问题会变化的量
    // 选择：让状态发生变化的行为
    // dp函数/数组的定义：给定目标金额n,返回凑出目标金额n所需的最少硬币个数
    int dp(vector<int>& coins, int amount)
    {
        // base case
        if(amount == 0)
            return 0;
        if(amount < 0)
            return -1;

        if(memo[amount] != -666)
            return memo[amount];

        int res = INT_MAX;
        for(int coin : coins)
        {
            int subProblem = dp(coins, amount - coin);
            if(subProblem == -1) continue;
            res = min(res, subProblem + 1);
        }

        // 将计算结果存入到备忘录中
        memo[amount] = (res == INT_MAX) ? -1 : res;

        return memo[amount];
    }
};


class Solution {
public:

    vector<int> memo; // 备忘录

    int coinChange(vector<int>& coins, int amount) 
    {
        memo.resize(amount + 1); // 最多有amount种结果(全是面值为1的硬币)

        fill(memo.begin(), memo.end(), -666);

        return dp(coins, amount);
    }

    int dp(vector<int>& coins, int amount)
    {
        // base case
        if(amount == 0)
            return 0;
        if(amount < 0)
            return -1;

        if(memo[amount] != -666)
            return memo[amount];

        int res = INT_MAX;
        for(int coin : coins)
        {
            int subProblem = dp(coins, amount - coin);
            if(subProblem == -1) continue;
            res = min(res, subProblem + 1);
        }

        memo[amount] = (res == INT_MAX) ? -1 : res;
        return memo[amount];
        
    }

};


class Solution {
public:

    // vector<int> memo; // 充当备忘录

    // int coinChange(vector<int>& coins, int amount) 
    // {
    //     memo.resize(amount + 1);
    //     fill(memo.begin(), memo.end(), -666);

    //     return dp(coins, amount);
    // }

    // // 状态：原问题和子问题中会变化的量- 需要凑齐的金额 - amount
    // // 选择：引起状态发生变化的条件 - 硬币的面值 - coins - coin
    // // dp函数/数组的定义：给你一个目标金额n，返回凑齐目标金额n所需的最少硬币个数
    // int dp(vector<int>& coins, int amount)
    // {
    //     // base case
    //     if(amount == 0)
    //         return 0;
    //     if(amount < 0)
    //         return -1;

    //     if(memo[amount] != -666)
    //         return memo[amount];

    //     int res = INT_MAX;
    //     for(int coin : coins)
    //     {
    //         int subProblem = dp(coins, amount - coin);
    //         if(subProblem == -1) continue;
    //         res = min(res, subProblem + 1);
    //     }

    //     memo[amount] = (res == INT_MAX) ? -1 : res;
    //     return memo[amount];
    // }

    int coinChange(vector<int>& coins, int amount) 
    {
        // int Max = amount + 1;
        // vector<int> dp(amount + 1, Max);
        vector<int> dp(amount + 1, amount + 1); // 开辟空间和初始值都是amount+1

        // base case
        dp[0] = 0;

        // 第一层for循环表示要找的钱
        for (int i = 1; i <= amount; ++i) 
        {
            // // 第二层for循环表示找钱的方式-遍历每一个面值硬币
            // for (int j = 0; j < (int)coins.size(); ++j) 
            // {
            //     // 确保 你要找的钱 大于找钱的方式（目标金额小于任意面值的硬币时还找毛啊）
            //     if (coins[j] <= i) 
            //     {
            //         dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            //     }
            // }

            // 第二层for循环表示找钱的方式-遍历每一个面值硬币
            for(int coin : coins)
            {
                // 保证要找的钱大于面值的大小
                if(i < coin) continue;

                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }

};


class Solution {
public:
    int numSquares(int n) 
    {
        vector<int> dp(n + 1);

        // base case
        dp[0] = 0;

        for(int i = 1;i <= n; i++)
        {
            dp[i] = i; // 全为1时最多i个

            for(int j = 1; j * j <= i; j++)
            {
                dp[i] = min(dp[i], dp[i - j * j] + 1);
            }
        }

        return dp[n];
    }
};


class Solution {
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        // dp[i]表示以nums[i]结尾的最长递增子序列的长度
        vector<int> dp(nums.size(), 1);

        // base case - dp数组全部初始化成1

        for(int i = 0; i < nums.size(); i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        int res = 0;
        for(int i = 0; i < dp.size(); i++)
        {
            res = max(res, dp[i]);
        }

        return res;
    }
};


class Solution {
public:
    int maxSubArray(vector<int>& nums)
    {
        // 滑动窗口解法
        // 1. 什么时候扩大窗口？
        // 2. 什么时候缩小窗口？
        // 3. 什么时候更新答案？

        int left = 0, right = 0;
        int windowSum = 0, maxSum = INT_MIN;

        while(right < nums.size())
        {
            windowSum += nums[right];

            right++;

            maxSum = windowSum > maxSum ? windowSum : maxSum;

            while(windowSum < 0)
            {
                windowSum -= nums[left];// 此时该元素一定是负数
                
                left++;
            }
        }

        return maxSum;
    }
};


class Solution {
public:
    // int maxSubArray(vector<int>& nums)
    // {
    //     // 滑动窗口解法
    //     // 1. 什么时候扩大窗口？
    //     // 2. 什么时候缩小窗口？
    //     // 3. 什么时候更新答案？

    //     int left = 0, right = 0;
    //     int windowSum = 0, maxSum = INT_MIN;

    //     while(right < nums.size())
    //     {
    //         windowSum += nums[right];

    //         right++;

    //         maxSum = windowSum > maxSum ? windowSum : maxSum;

    //         while(windowSum < 0)
    //         {
    //             windowSum -= nums[left];// 此时该元素一定是负数
                
    //             left++;
    //         }
    //     }

    //     return maxSum;
    // }

    int maxSubArray(vector<int>& nums)
    {
        // dp[i]表示以nums[i]结尾的最大数组和
        vector<int> dp(nums.size());

        if(nums.empty())
            return 0;

        // base case
        dp[0] = nums[0];

        for(int i = 1; i < nums.size(); i++)
        {
            // 要么自成一派，要么与前面的子数组合并
            dp[i] = max(nums[i], nums[i] + dp[i - 1]);
        }

        int res = INT_MIN;
        for(int i = 0; i < dp.size(); i++)
        {
            res = max(res, dp[i]);
        }

        return res;
    }
};


class Solution {
public:
    // int lengthOfLIS(vector<int>& nums) 
    // {
    //     // dp[i]表示以nums[i]结尾的最长递增子序列的长度
    //     vector<int> dp(nums.size(), 1);

    //     // base case - dp数组初始值全部置为1

    //     for(int i = 0; i < nums.size(); i++)
    //     {
    //         for(int j = 0; j < i; j++)
    //         {
    //             if(nums[i] > nums[j])
    //                 dp[i] = max(dp[i], dp[j] + 1);
    //         }
    //     }

    //     int res = 0;
    //     for(int i = 0; i < dp.size(); i++)
    //     {
    //         res = max(res, dp[i]);
    //     }

    //     return res;
    // }

    int lengthOfLIS(vector<int>& nums)
    {
        // dp[i]表示以nums[i]结尾的最长递增子序列的长度
        vector<int> dp(nums.size(), 1);

        // base case - dp数组初始值全部设置为1，还用说原因吗，至少是1

        for(int i = 0; i < nums.size(); i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(nums[i] > nums[j])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }

        int res = INT_MIN;
        for(int i = 0; i < dp.size(); i++)
        {
            res = max(res, dp[i]);
        }

        return res;
    }
};


class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) 
    {
        // dp函数的定义：从第一行(matrix[0][..])开始到matrix[i][j]的最小路径和为dp(matrix,i,j)
        int n = matrix.size();

        vector<vector<int>> memo(n, vector<int>(n, 66666)); // 最大路径和不可能超过10000
        int res = INT_MAX;

        for(int j = 0; j < n; j++)
        {
            // 答案一定在dp(matrix, n - 1, ..)中
            res = min(res, dp(matrix, memo, n - 1, j));
        }

        return res;
    }

    int dp(vector<vector<int>>& matrix, vector<vector<int>>& memo, int row, int col)
    {
        // 检查索引
        if(row < 0 || col < 0 || row >= matrix.size() || col >= matrix[0].size())
            return 99999;
        
        // base case
        if(row == 0)
            return matrix[0][col];

        // 检查备忘录
        if(memo[row][col] != 66666)
            return memo[row][col];

        // 进行状态转移
        memo[row][col] = matrix[row][col] + threeMin(
            dp(matrix, memo, row - 1, col),
            dp(matrix, memo, row - 1, col - 1),
            dp(matrix, memo, row - 1, col + 1)
        );

        return memo[row][col];
    }

    int threeMin(int first, int second, int third)
    {
        return min(first, min(second, third));
    }
};


class Solution {
public:

    // vector<vector<int>> memo;

    int minDistance(string word1, string word2) 
    {
        // dp函数的定义：返回s1[0..i]和s2[0..j]的最小编辑距离

        int m = word1.size(), n = word2.size();

        vector<vector<int>> memo(m, vector<int>(n, -1));

        // memo = vector<vector<int>>(m, vector<int>(n, -1));

        return dp(memo, word1, m - 1, word2, n - 1);
    }

    int dp(vector<vector<int>>& memo, string s1, int i, string s2, int j)
    {
        // base case 
        if(i == -1) return j + 1;
        if(j == -1) return i + 1;

        // 查看备忘录
        if(memo[i][j] != -1)
            return memo[i][j];

        // 进行状态转移
        if(s1[i] == s2[j])
        {
            memo[i][j] = dp(memo, s1, i - 1, s2, j - 1);
        }
        else
        {
            memo[i][j] = threeMin(dp(memo, s1, i, s2, j - 1) + 1/*插入*/,
                                  dp(memo, s1, i - 1, s2, j) + 1/*删除*/,
                                  dp(memo, s1, i -  1, s2, j - 1) + 1/*替换*/
                                  );
        }

        return memo[i][j];
    }

    int threeMin(int first, int second, int third)
    {
        return min(first, min(second, third));
    }
};


class Solution {
public:
    int minDistance(string word1, string word2) 
    {
        // dp函数的定义：返回s1[0..i]和s2[0..j]的最小操作数
        int m = word1.size(), n = word2.size();

        vector<vector<int>> memo(m, vector<int>(n, -1));

        return dp(memo, word1, m - 1, word2, n - 1);
    }

    int dp(vector<vector<int>>& memo, string s1, int i, string s2, int j)
    {
        // base case - 当i走到s1末尾或者j走到s2末尾，直接返回另一个字符串的长度
        if(i == -1) return j + 1;
        if(j == -1) return i + 1;

        if(memo[i][j] != -1)
            return memo[i][j];

        // 进行状态转移
        if(s1[i] == s2[j])
        {
            memo[i][j] = dp(memo, s1, i - 1, s2, j - 1);
        }
        else
        {
            memo[i][j] = threeMin(dp(memo, s1, i, s2, j - 1) + 1/*插入*/,
                                  dp(memo, s1, i - 1, s2, j) + 1/*删除*/,
                                  dp(memo, s1, i - 1, s2, j - 1) + 1/*替换*/
                                  );
        }

        return memo[i][j];
    }

    int threeMin(int first, int second, int third)
    {
        return min(first, min(second, third));
    }
};


class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) 
    {
        // dp函数的定义：s1[i..]和s2[j..]的最长公共子序列
        int m = text1.size(), n = text2.size();
        vector<vector<int>> memo(m, vector<int>(n, -1));

        return dp(memo, text1, 0, text2, 0);
    }

    int dp(vector<vector<int>>& memo, string& s1, int i, string& s2, int j)
    {
        // base case
        if(i == s1.size() || j == s2.size())
            return 0;

        // 查看备忘录
        if(memo[i][j] != -1)
            return memo[i][j];

        if(s1[i] == s2[j])
        {
            memo[i][j] = 1 + dp(memo, s1, i + 1, s2, j + 1);
        }
        else
        {
            memo[i][j] = max(dp(memo, s1, i + 1, s2, j), 
                             dp(memo, s1, i, s2, j + 1));
        }

        return memo[i][j];
    }
};


class Solution {
public:
    int minDistance(string word1, string word2) 
    {
        // dp函数的定义：s1[0..i]和s2[0..j]的最小操作数
        int m = word1.size(), n = word2.size();

        vector<vector<int>> memo(m, vector<int>(n, -1));

        return dp(memo, word1, m - 1, word2, n - 1);
    }

    int dp(vector<vector<int>>& memo, string& s1, int i, string& s2, int j)
    {
        // base case
        if(i == -1) return j + 1; // 插入
        if(j == -1) return i + 1; // 删除

        // 查看备忘录
        if(memo[i][j] != -1)
        {
            return memo[i][j];
        }

        // 进行状态转移
        if(s1[i] == s2[j])
        {
            memo[i][j] = dp(memo, s1, i - 1, s2, j - 1);
        }
        else
        {
            memo[i][j] = threeMin(dp(memo, s1, i, s2, j - 1) + 1, 
                                  dp(memo, s1, i - 1, s2, j) + 1, 
                                  dp(memo, s1, i - 1, s2, j - 1) + 1);

        }

        return memo[i][j];
    }

    int threeMin(int first, int second, int third)
    {
        return min(first, min(second, third));
    }
};


class Solution {
public:

    vector<vector<int>> memo;

    int minDistance(string word1, string word2) 
    {
        // dp函数的定义：s1[0..i]和s2[0..j]的最小操作数
        int m = word1.size(), n = word2.size();

        memo = vector<vector<int>>(m, vector<int>(n, -1));

        return dp(word1, m - 1, word2, n - 1);
    }

    int dp(string& s1, int i, string& s2, int j)
    {
        // base case
        if(i == -1) return j + 1;
        if(j == -1) return i + 1;

        // 查看备忘录
        if(memo[i][j] != -1)
            return memo[i][j];

        // 进行状态转移
        if(s1[i] == s2[j])
        {
            memo[i][j] = dp(s1, i - 1, s2, j - 1);
        }
        else
        {
            memo[i][j] = threeMin(dp(s1, i, s2, j - 1) + 1, 
                            dp(s1, i - 1, s2, j) + 1,
                            dp(s1, i - 1, s2, j - 1) + 1);
        }

        return memo[i][j];
    }

    int threeMin(int first, int second, int third)
    {
        return min(first, min(second, third));
    }
};


class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) 
    {
        // dp函数的定义：s1[0..i]和s2[0..j]的最长公共子序列LCS
        int m = text1.size(), n = text2.size();

        vector<vector<int>> memo(m, vector<int>(n, -1));

        return dp(memo, text1, 0, text2, 0);
    }

    int dp(vector<vector<int>>& memo, string& s1, int i, string& s2, int j)
    {
        // base case
        if(i == s1.size() || j == s2.size())
            return 0;

        if(memo[i][j] != -1)
            return memo[i][j];

        // 进行状态转移
        if(s1[i] == s2[j])
        {
            memo[i][j] = dp(memo, s1, i + 1, s2, j + 1) + 1;
        }
        else
        {
            memo[i][j] = max(dp(memo, s1, i + 1, s2, j), 
                             dp(memo, s1, i, s2, j + 1));
        }

        return memo[i][j];
    }
};


class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) 
    {
        // dp函数的定义：s1[0..i]和s2[0..j]的最长公共子序列LCS
        int m = text1.size(), n = text2.size();

        vector<vector<int>> memo(m, vector<int>(n, -1));

        return dp(memo, text1, 0, text2, 0);
    }

    int dp(vector<vector<int>>& memo, string& s1, int i, string& s2, int j)
    {
        // base case
        if(i == s1.size() || j == s2.size())
            return 0;

        if(memo[i][j] != -1)
            return memo[i][j];

        // 进行状态转移
        if(s1[i] == s2[j])
        {
            memo[i][j] = dp(memo, s1, i + 1, s2, j + 1) + 1;
        }
        else
        {
            memo[i][j] = max(dp(memo, s1, i + 1, s2, j), 
                             dp(memo, s1, i, s2, j + 1));
        }

        return memo[i][j];
    }
};


class Solution {
public:

    vector<vector<int>> memo;

    int minDistance(string word1, string word2) 
    {
        int m = word1.size(), n = word2.size();

        memo = vector<vector<int>>(m, vector<int>(n, -1));

        int lcs = longestCommonSubstring(word1, word2);

        return m - lcs + n - lcs;
    }

    int longestCommonSubstring(string& s1, string& s2)
    {
        return dp(s1, 0, s2, 0);
    }

    int dp(string& s1, int i, string& s2, int j)
    {
        // base case
        if(i == s1.size() || j == s2.size())
            return 0;

        // 查看备忘录
        if(memo[i][j] != -1)
            return memo[i][j];

        // 进行状态转移
        if(s1[i] == s2[j])
        {
            memo[i][j] = dp(s1, i + 1, s2, j + 1) + 1;
        }
        else
        {
            memo[i][j] = max(dp(s1, i + 1, s2, j), 
                             dp(s1, i, s2, j + 1));
        }

        return memo[i][j];
    }
};


class Solution {
public:

    vector<vector<int>> memo;

    int minimumDeleteSum(string s1, string s2) 
    {
        // dp函数的定义：s1[0..i]和s2[0..j]相同字符串的所需删除字符的ACSII值的最小和

        int m = s1.size(), n = s2.size();
        memo = vector<vector<int>>(m, vector<int>(n, -1));

        return dp(s1, 0, s2, 0);
    }

    int dp(string& s1, int i, string& s2, int j)
    {
        int res = 0;

        // base case
        if(i == s1.size()) // 如果s1结束了，s2全部都得删除
        {
            for(; j < s2.size(); j++)
            {
                res += s2[j];
            }

            return res;
        }
        if(j == s2.size())
        {
            for(; i < s1.size(); i++)
            {
                res += s1[i];
            }

            return res;
        }

        if(memo[i][j] != -1)
            return memo[i][j];

        if(s1[i] == s2[j])
        {
            memo[i][j] = dp(s1, i + 1, s2, j + 1);
        }
        else
        {
            memo[i][j] = min(dp(s1, i + 1, s2, j) + s1[i], 
                             dp(s1, i, s2, j +1) + s2[j]);
        }

        return memo[i][j];
    }   
};

-----------------------------------------------------------------
int n = array.length;

int[] dp = new int[n];

for(int i = 1; i < n; i++)
	for(int j = 0; j < i; j++)
		dp[i] = 最值(dp[i], dp[j] + ...)
	}
}

在这个思路中dp数组的定义是：
在子数组arr[0..i]中，以arr[i]结尾的子序列的长度是dp[i]


int n = arr.length;
int[][] dp = new dp[n][n];

for(int i = 0; i < n; i++)
{
	for(int j = 0; j < n; j++)
	{
		if(arr[i] == arr[j])
			dp[i][j] = dp[i][j] + ...
		else
			dp[i][j] = 最值(...)
	}
}


涉及两个字符串/数组的场景，dp数组的定义如下：
	在子数组arr1[0..i]和子数组arr2[0..j]中，我们要求的子序列的长度为dp[i][j]

只涉及一个字符串/数组的场景，dp数组的定义如下：
	在子数组array[i..j]中，我们要求的子序列的长度为dp[i][j]

class Solution {
public:

    vector<vector<int>> memo;

    int longestPalindromeSubseq(string s) 
    {
        // dp函数的定义：在子串s[i..j]中，最长回文子序列的长度是dp(i, j)
        int m = s.size();

        memo = vector<vector<int>>(m, vector<int>(m, -1));

        return dp(s, 0, m - 1);
    }

    int dp(string& s, int i, int j)
    {
        // base case
        if(i < 0 || i >= s.size() || j < 0 || j >= s.size())
            return 0;

        if(memo[i][j] != -1)
            return memo[i][j];

        if(s[i] == s[j])
        {
            memo[i][j] = dp(s, i + 1, j - 1) + 1;
        }
        else
        {
            memo[i][j] = max(dp(s, i + 1, j), 
                             dp(s, i, j - 1));
        }

        return memo[i][j];
    }
};


class Solution {
public:

    vector<vector<int>> memo;

    int minInsertions(string s) 
    {
        return s.size() - longestPalindromeString(s);
    }

    int longestPalindromeString(string& s)
    {
        int m = s.size();

        memo = vector<vector<int>>(m, vector<int>(m, -1));

        return dp(s, 0, m - 1) / 2;
    }

    int dp(string& s, int i, int j)
    {
        // base case
        if(i < 0 || i >= s.size() || j < 0 || j >= s.size())
            return 0;

        if(memo[i][j] != -1)
            return memo[i][j];

        if(s[i] == s[j])
        {
            memo[i][j] = dp(s, i + 1, j - 1) + 2;
        }
        else
        {
            memo[i][j] = max(dp(s, i + 1, j), 
                             dp(s, i, j - 1));
        }

        return memo[i][j];
    }
};


class Solution {
public:

    vector<vector<int>> memo;

    bool canPartition(vector<int>& nums) 
    {
        int n = nums.size();

        memo = vector<vector<int>>(n, vector<int>(n, -1));

        int sum = 0;

        for(int num : nums)
            sum += num;

        if(sum % 2 != 0)
            return false; // 不满足条件

        int size = sum / 2;

        memo.assign(n, vector<int>(size + 1, -1)); // ?

        return dp(nums, n - 1, size);
    }

    // dp函数的定义：dp(i,size)表示前i个物品，当前背包的容量是size，若背包恰好装满返回true，否则返回false
    bool dp(vector<int>& nums, int i, int size)
    {
        int j = size;
        // base case
        if(i == -1) return false; // 没有物品
        if(j == 0) return true; // 没有容量

        if(memo[i][j] != -1)
            return memo[i][j];

        // 进行状态转移
        if(size - nums[i] >= 0)
        {
            memo[i][j] = dp(nums, i - 1, size) || dp(nums, i - 1, size-nums[i]);
        }
        else
        {
            memo[i][j] = dp(nums, i - 1, size);
        }

        return memo[i][j];
    }
};


class Solution {
public:

    vector<vector<int>> memo;

    bool canPartition(vector<int>& nums) 
    {
        int n = nums.size();

        memo = vector<vector<int>>(n, vector<int>(n, -1));

        int sum = 0;

        for(int num : nums)
            sum += num;

        if(sum %2 != 0) // 和为奇数不合题意
            return false;

        int size = sum / 2;

        memo.assign(n, vector<int>(size + 1, -1));

        return dp(nums, n - 1, size);
    }

    // dp函数的定义：dp(i, size)表示前i个物品，当前背包的容量是size，如若背包恰好满了返回true，反之返回false
    bool dp(vector<int>& nums, int i, int size)
    {
        int j = size;
        // base case
        if(i == -1) return false; // 表示没有物品
        if(size == 0) return true; // 背包的当前容量

        if(memo[i][j] != -1)
            return memo[i][j];

        // 进行状态转移
        if(size - nums[i] >= 0)
        {
            memo[i][j] = dp(nums, i - 1, size) || dp(nums, i - 1, size-nums[i]);
        }
        else
        {
            memo[i][j] = dp(nums, i - 1, size);
        }

        return memo[i][j];
    }

};


class Solution {
public:
    int change(int amount, vector<int>& coins) 
    {
        // dp数组的定义：若只使用前i个物品(可以重复使用)，当背包容量为j时，可以有dp[i][j]种方法
        int n = coins.size();

        vector<vector<int>> dp(n + 1, vector<int>(amount + 1));

        // base case
        for(int i = 0; i <= n; i++)
        {
            dp[i][0] = 1;
        }

        // 进行状态转移
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= amount; j++)
            {
                if(j - coins[i - 1] >= 0)
                {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
                }
                else
                {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n][amount];
    }
};

class Solution {
public:

    vector<int> memo;

    int rob(vector<int>& nums) 
    {
        int n = nums.size();

        memo = vector<int>(n, -1);

        // dp函数的定义：nums[start..]的最大值
        return dp(nums, 0);
    }

    int dp(vector<int>& nums, int start)
    {
        // base case
        if(start >= nums.size())
            return 0;

        if(memo[start] != -1)
            return memo[start];

        memo[start] = max(dp(nums, start + 1), nums[start] + dp(nums, start + 2));

        return memo[start];
    }
};


class Solution {
public:
    int rob(vector<int>& nums) 
    {
        int n = nums.size();

        if(n == 1)
            return nums[0];

        vector<int> memo1(n, -1);
        vector<int> memo2(n, -1);

        return max(
                  dp(nums, 0, n - 2, memo1),
                  dp(nums, 1, n - 1, memo2));
    }

    int dp(vector<int>& nums, int start, int end, vector<int>& memo)
    {
        // base case
        if(start > end)
            return 0;

        if(memo[start] != -1)
            return memo[start];

        int res = 0;
        res = max(dp(nums, start + 1, end, memo), nums[start] + dp(nums, start + 2, end, memo));

        memo[start] = res;

        return res;
    }
};



class Solution {
public:

    vector<int> memo;

    int rob(vector<int>& nums) 
    {
        int n = nums.size();

        memo = vector<int>(n, -1);

        return dp(nums, 0);
    }

    // dp函数的定义：nums[start..]的最大值
    int dp(vector<int>& nums, int start)
    {
        // base case
        if(start >= nums.size())
            return 0;

        if(memo[start] != -1)   
            return memo[start];

        memo[start] = max(dp(nums, start + 1), nums[start] + dp(nums, start + 2));

        return memo[start];
    }
};


class Solution {
public:
    int rob(vector<int>& nums) 
    {
        int n = nums.size();

        if(n == 1)
            return nums[0];

        vector<int> memo1(n, -1);
        vector<int> memo2(n, -1);

        return max(dp(nums, 0, n - 2, memo1), dp(nums, 1, n - 1, memo2));
    }

    int dp(vector<int>& nums, int start, int end, vector<int>& memo)
    {
        // base case
        if(start > end)
            return 0;

        if(memo[start] != -1)
            return memo[start];

        memo[start] = max(dp(nums, start + 1, end, memo), 
                          dp(nums, start + 2, end, memo) + nums[start]);

        return memo[start];
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) 
    {
        vector<int> res = dp(root);

        return max(res[0], res[1]);
    }

    // 返回一个大小为2的数组arr
    // arr[0]表示不抢root的话，得到的最大钱数
    // arr[1]表示抢root的话，得到的最大钱数
    vector<int> dp(TreeNode* root)
    {
        if(root == nullptr)
            return {0, 0};

        vector<int> left = dp(root->left);
        vector<int> right = dp(root->right);

        // 抢，下家就不能抢了
        int rob = root->val + left[0] + right[0];
        // 不抢，下家可抢可不抢，取决于收益大小
        int notRob = max(left[0], left[1]) + max(right[0], right[1]);

        return {notRob, rob};
    }
};

// class Solution {
//     int rob(TreeNode root) {
//         int[] res = dp(root);
//         return Math.max(res[0], res[1]);
//     }
//     /* 返回一个大小为 2 的数组 arr     arr[0] 表示不抢 root 的话，得到的最大钱数     arr[1] 表示抢 root 的话，得到的最大钱数 */
//     int[] dp(TreeNode root) {
//         if (root == null)
//             return new int[]{0, 0};
//         int[] left = dp(root.left);
//         int[] right = dp(root.right);
//         // 抢，下家就不能抢了
//         int rob = root.val + left[0] + right[0];
//         // 不抢，下家可抢可不抢，取决于收益大小
//         int not_rob = Math.max(left[0], left[1])
//                     + Math.max(right[0], right[1]);

//         return new int[]{not_rob, rob};
//     }
// }


// 股票系列问题通用状态转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i])
	      max(  今天选择rest，    今天选择sell)

dp[i][k][1] = max(dp([i-1][k][1], dp[i-1][k-1][0] - prices[i])
	      max(  今天选择rest，    今天选择buy)

// 通用base
dp[-1][..][0] = dp[..][0][0] = 0;
dp[-1][..][1] = dp[..][0][1] = -infinity;


// ----------------------------------------------------------------
// 买卖股票的base case：
dp[-1][..][0] = 0;
// 因为i是从0开始的，所以i==-1意味着还没开始，这时候的利润当然是0

dp[-1][..][1] = -infinity;
// 因为还没有开始的时候是不能持有股票的，由于我们的算法是要求一个最大值，所以我们初始值设为一个最小值，方便去最大值。

dp[..][0][0] = 0;
// 因为k是从1开始的，所以k=0意味着根本不允许交易，这时候利润当然是0

dp[..][0][1] = -infinity;
// 不允许交易的情况下是不可能持有股票的。
// 因为我们的算法是要求一个最大值，所以初始值设为一个最小值，方便取最大值。


// 状态转移方程：
base case:
dp[-1][..][0] = dp[..][0][0] = 0;
dp[-1][..][1] = dp[..][0][1] = -infinity;

状态转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);

class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();

        vector<vector<int>> dp(n, vector<int>(2));

        for(int i = 0; i < n; i++)
        {
            // base case
            if(i - 1 == -1)
            {
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], -prices[i]);
        }

        return dp[n-1][0];
    }
};


class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();

        vector<vector<int>> dp(n, vector<int>(2, 0));

        for(int i = 0; i < n; i++)
        {
            if(i - 1 == -1)
            {
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }

            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }

        return dp[n-1][0];
    }
};


class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();

        vector<vector<int>> dp(n, vector<int>(2, 0));

        for(int i = 0; i < n; i++)
        {
            // base case1
            if(i - 1 == -1)
            {
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }
            // base case2
            if(i - 2 == -1)
            {
                dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
                dp[i][1] = max(dp[i-1][1], -prices[i]);
                continue;
            }

            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i]);
        }

        return dp[n-1][0];
    }
};


class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) 
    {
        int n = prices.size();

        vector<vector<int>> dp(n, vector<int>(2));

        for(int i = 0; i < n; i++)
        {
            // base case
            if(i - 1 == -1)
            {
                dp[i][0] = 0; // = max(dp[i-1][0], dp[i-1][1] + prices[i]); ???
                dp[i][1] = -prices[i] - fee; // = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee);
                continue;
            }

            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee);
        }

        return dp[n-1][0];
    }
};


class Solution {
public:

    // k == 1时的情况
    int maxProfit(vector<int>& prices) {
        
        int n = prices.size();

        if(n <= 0) // 注意记得加上这一句哦！
            return 0;

        vector<vector<int>> dp(n, vector<int>(2));

        for(int i = 0; i < n; i++)
        {
            // base case
            if(i - 1 == -1)
            {
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], -prices[i]);
        }

        return dp[n-1][0];
    }
};


class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();

        // if(n == 0)
        //     return 0;

        vector<vector<int>> dp(n, vector<int>(2));

        for(int i = 0; i < n; i++)
        {
            // base case
            if(i - 1 == -1)
            {
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }

            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], -prices[i]);
        }

        return dp[n-1][0];
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();

        if(n <= 0)
            return 0;

        vector<vector<int>> dp(n, vector<int>(2, 0));

        for(int i = 0; i < n; i++)
        {
            // base case
            if(i - 1 == -1)
            {
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }

            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }

        return dp[n-1][0];
    }
};


class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        int maxK = 2, n = prices.size();

        vector<vector<vector<int>>> dp(n, vector<vector<int>>(maxK+1, vector<int>(2, 0)));

        for(int i = 0; i < n; i++)
        {
            for(int k = 1; k <= maxK; k++)
            {
                // base case
                if(i - 1 == -1)
                {
                    dp[i][k][0] = 0;
                    dp[i][k][1] = -prices[i];
                    continue; // 记得添加这一步操作
                }

                dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
                dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
            }
           
        }

        return dp[n-1][maxK][0];
    }
};

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) 
    {
        int n = prices.size();

        if(n <= 0)
            return 0;

        if(k > n / 2) // K为正无穷的情况-封装之前的函数
            return maxProfitMaxK(prices);

        vector<vector<vector<int>>> dp(n, vector<vector<int>>(k+1, vector<int>(2, 0)));

        // k == 0的情况
        for(int i = 0; i < n; i++)
        {
            // base case
            if(i - 1 == -1)
            {
                dp[i][0][0] = 0;
                dp[i][0][1] = INT_MIN;
                continue;
            }
        }

        for(int i = 0; i < n; i++)
        {
            for(int j = 1; j <= k; j++)
            {
                if(i - 1 == -1)
                {
                    // base case
                    dp[i][j][0] = 0;
                    dp[i][j][1] = -prices[i];
                    continue;
                }

                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
            }
        }

        return dp[n-1][k][0];
    }


    int maxProfitMaxK(vector<int>& prices)
    {
        int n = prices.size();

        vector<vector<int>> dp(n, vector<int>(2, 0));

        for(int i = 0; i < n; i++)
        {
            // base case
            if(i - 1 == -1)
            {
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }

            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }

        return dp[n-1][0];
    }
};


class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();

        vector<vector<int>> dp(n, vector<int>(2, 0));

        for(int i = 0; i < n; i++)
        {
            // base case1
            if(i - 1 == -1)
            {
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }

            // base case2
            if(i - 2 == -1)
            {
                dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
                dp[i][1] = max(dp[i-1][1], -prices[i]);
                continue;
            }

            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i]);
        }

        return dp[n-1][0];
    }
};


class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) 
    {
        int n = prices.size();

        vector<vector<int>> dp(n, vector<int>(2, 0));

        for(int i = 0; i < n; i++)
        {
            // base case
            if(i - 1 == -1)
            {
                dp[i][0] = 0;
                dp[i][1] = -prices[i] - fee;
                continue;
            }

            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee);
        }

        return dp[n-1][0];
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();

        if(n <= 0)
            return 0;

        vector<vector<int>> dp(n, vector<int>(2, 0));

        for(int i = 0; i < n; i++)
        {
            // base case
            if(i - 1 == -1)
            {
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }

            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], -prices[i]);
        }

        return dp[n-1][0];
    }
};


// 动态规划算法本质上就是穷举状态，然后在选择中选择最优解。
// 动态规划算法本质上就是穷举状态，然后在选择中选择最优解。
// 动态规划算法本质上就是穷举状态，然后在选择中选择最优解。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) 
    {
        int n = prices.size();

        vector<vector<vector<int>>> dp(n, vector<vector<int>>(k + 1, vector<int>(2)));

        if(k > n / 2)
        {
            return _maxProfit(prices);
        }

        // k == 0
        for(int i = 0; i < n; i++)
        {
            if(i - 1 == -1)
            {
                dp[i][0][0] = 0;
                dp[i][0][1] = INT_MIN;
                continue;
            }
        }

        for(int i = 0; i < n; i++)
        {
            for(int j = 1; j <= k; j++)
            {
                // base case
                if(i - 1 == -1)
                {
                    dp[i][j][0] = 0;
                    dp[i][j][1] = -prices[i];
                    continue;
                }

                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
            }
        }

        return dp[n-1][k][0];
    }

    int _maxProfit(vector<int>& prices)
    {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2));

        for(int i = 0; i < n; i++)
        {
            if(i - 1 == -1)
            {
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }

            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }

        return dp[n-1][0];
    }
};


class Solution {
public:
    int rob(vector<int>& nums) 
    {
        int n = nums.size();

        if(n == 1)
            return nums[0];

        vector<int> memo1(n, -1);
        vector<int> memo2(n, -1);

        return max(dp(nums, 0, n - 2, memo1), dp(nums, 1, n - 1, memo2));
    }

    int dp(vector<int>& nums, int start, int end, vector<int>& memo)
    {
        if(start > end)
        {
            return 0;
        }

        if(memo[start] != -1)
            return memo[start];

        memo[start] = max(dp(nums, start+1, end, memo), nums[start]+dp(nums, start+2, end, memo));

        return memo[start];
    }
};


class Solution {
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        // dp数组的定义：dp[i]表示以nums[i]结尾的最长递增子序列的长度
        // 初始值设为1是因为至少为1
        int n = nums.size();

        vector<int> dp(n, 1);

        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                // 寻找nums[0..j-1] 中比 nums[i] 小的元素
                // 即可形成长度为dp[j]+1, 且以nums[i]结尾的最长递增子序列
                if(nums[j] < nums[i])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        // 遍历dp数组找到最大值，即为最长递增子序列
        int res = INT_MIN;
        for(int i = 0; i < n; i++)
        {
            res = max(res, dp[i]);
        }

        return res;
    }
};


class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) 
    {
        int n = envelopes.size();

        // 对宽度按升序排列，如果宽度相同，则按高度将降序排列
        // 然后再在高度数组中找TIS即可
        sort(envelopes.begin(), envelopes.end(), [] (vector<int>& a, vector<int>& b) 
        {
            if(a[0] == b[0])
                return a[1] > b[1];
            else
                return a[0] < b[0];
        }
        );

        vector<int> height(n);
        for(int i = 0; i < n; i++)
        {
            height[i] = envelopes[i][1];
        }

        return lengthTIS(height);
    }

    int lengthTIS(vector<int>& nums)
    {
        int n = nums.size();

        int piles = 0; // 牌堆数
        vector<int> top(n); // 牌堆数组

        for(int i = 0; i < n; i++)
        {
            int poker = nums[i]; // 要处理的牌

            int left = 0, right = piles - 1;
            while(left <= right)
            {
                int mid = left + (right - left) / 2;

                if(top[mid] < poker)
                    left = mid + 1;
                else if(top[mid] > poker)
                    right = mid - 1;
                else if(top[mid] == poker)
                    // 收缩右侧边界
                    right = mid - 1;
            }

            // 没有找到合适的牌堆，牌堆++
            if(left == piles) piles++;

            // 将该牌放到牌堆中
            top[left] = poker;
        }

        return piles;


        // int n = nums.size();

        // // dp数组的定义: dp[i]表示以nums[i]结尾的最长连续子序列的长度
        // vector<int> dp(n, 1);

        // for(int i = 0; i < n; i++)
        // {
        //     for(int j = 0; j < i; j++)
        //     {
        //         // 寻找nums[0..j]比nums[i]小的元素
        //         // 即可找到长度为dp[j]+1且以nums[i]结尾的最长连续子序列
        //         if(nums[j] < nums[i])
        //             dp[i] = max(dp[i], dp[j] + 1);
        //     }
        // }

        // // 遍历dp数组找最大值即为最长连续子序列的长度
        // int ret = INT_MIN;
        // for(int i = 0; i < n; i++)
        // {
        //     ret = max(ret, dp[i]);
        // }

        // return ret;
    }
};


class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) 
    {
        int n = envelopes.size();

        // 先按照宽度升序排列，如果宽度相同，则按照高度降序排列
        sort(envelopes.begin(), envelopes.end(), [] (vector<int>& a, vector<int>& b)
        {
            if(a[0] == b[0])
            {
                return a[1] > b[1];
            }
            else
            {
                return a[0] < b[0];
            }
        }
        );

        vector<int> height(n);
        for(int i = 0; i < n; i++)
        {
            height[i] = envelopes[i][1];
        }

        return lengthLIS(height);
    }

    int lengthLIS(vector<int>& nums)
    {
        int piles = 0; // 牌堆数
        vector<int> top(nums.size()); // 牌堆数组

        for(int i = 0; i < nums.size(); i++)
        {
            int poker = nums[i]; // 要处理的牌

            int left = 0, right = piles - 1;

            // 搜索左侧边界
            while(left <= right)
            {
                int mid = left + (right - left) / 2;

                if(top[mid] < poker)
                {
                    left = mid + 1;
                }
                else if(top[mid] > poker)
                {
                    right = mid - 1;
                }
                else if(top[mid] == poker)
                {
                    // 收缩右侧边界
                    right = mid - 1;
                }
            }

            // 没有找到合适的牌堆，牌堆++
            if(left == piles)
                piles++;

            // 将该牌插入到牌堆中
            top[left] = poker;
        }

        return piles;
    }
};


class Solution {
public:

    vector<vector<int>> memo;

    int minDistance(string word1, string word2) 
    {
        int m = word1.size(), n = word2.size();

        memo = vector<vector<int>>(m, vector<int>(n, -1));

        // dp函数的定义：返回s1[0,i]和s2[0,j]的最少操作数
        return dp(word1, m - 1, word2, n - 1);
    }

    int dp(string& s1, int i, string& s2, int j)
    {
        if(i == -1) return j + 1;
        if(j == -1) return i + 1;

        if(memo[i][j] != -1)
            return memo[i][j];

        if(s1[i] == s2[j])
        {
            memo[i][j] = dp(s1, i - 1, s2, j - 1);
        }
        else
        {
            memo[i][j] = threeMin(dp(s1, i, s2, j - 1) + 1/*插入*/,
                                  dp(s1, i - 1, s2, j) + 1/*删除*/,
                                  dp(s1, i - 1, s2, j - 1) + 1/*替换*/);
        }

        return memo[i][j];
    }

    int threeMin(int first, int second, int third)
    {
        return min(first, min(second, third));
    }
};


class Solution {
public:
    int maxSales(vector<int>& sales) 
    {
      int n = sales.size();
      if(n == 0)
        return 0;

      // dp数组的定义：dp[i]表示以nums[i]结尾的最大连续子数组的和
      vector<int> dp(n);

      // base case
      dp[0] = sales[0];

      for(int i = 1; i < n; i++)
      {
        dp[i] = max(sales[i], sales[i] + dp[i-1]);
      }

      int ret = INT_MIN;

      for(int i = 0; i < n; i++)
      {
        ret = max(ret, dp[i]);
      }

      return ret;
    }
};

class Solution {
public:

    vector<vector<int>> memo;

    int minimumDeleteSum(string s1, string s2) 
    {
        int m = s1.size(), n = s2.size();

        memo = vector<vector<int>>(m, vector<int>(n, -1));

        // dp函数的定义：返回s1[i..]和s2[j..]字符串时的所需要删除字符的ASCII值的最小和
        return dp(s1, 0, s2, 0);
    }

    int dp(string& s1, int i, string& s2, int j)
    {
        int ret = 0;

        // base case
        if(i == s1.size())
        {
            for(; j < s2.size(); j++)
            {
                ret += s2[j];
            }
            return ret;
        }
        if(j == s2.size())
        {
            for(; i < s1.size(); i++)
            {
                ret += s1[i];
            }
            return ret;
        }

        if(memo[i][j] != -1)
            return memo[i][j];

        if(s1[i] == s2[j])
        {
            memo[i][j] = dp(s1, i + 1, s2, j + 1);
        }
        else
        {
            memo[i][j] = min((int)s1[i] + dp(s1, i + 1, s2, j), 
                             (int)s2[j] + dp(s1, i, s2, j + 1));
        }

        return memo[i][j];
    }
};

class Solution {
public:

    vector<vector<int>> memo;

    int minDistance(string word1, string word2) 
    {
        int m = word1.size(), n = word2.size();

        memo = vector<vector<int>>(m, vector<int>(n, -1));

        // dp函数的定义：返回将s1[0,i]转换为s2[0,j]做使用的最少操作数
        return dp(word1, m - 1, word2, n - 1);
    }

    int dp(string& s1, int i, string& s2, int j)
    {
        if(i == -1) return j + 1;
        if(j == -1) return i + 1;

        if(memo[i][j] != -1)
            return memo[i][j];

        if(s1[i] == s2[j])
        {
            memo[i][j] = dp(s1, i - 1, s2, j - 1);
        }
        else
        {
            memo[i][j] = threeMin(dp(s1, i - 1, s2, j) + 1, 
                                  dp(s1, i, s2, j - 1) + 1, 
                                  dp(s1, i - 1, s2, j - 1) + 1);
        }

        return memo[i][j];
    }

    int threeMin(int a, int b, int c)
    {
        return min(a, min(b, c));
    }
};


class Solution {
public:

    vector<string> res;
    string track;

    // 建立数字到字母的映射
    vector<string> valToIndex = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    vector<string> letterCombinations(string digits) 
    {
        if(digits.empty())
            return res;

        backtrack(digits, 0);

        return res;
    }

    void backtrack(string& digits, int start)
    {
        if(track.size() == digits.size())
        {
            res.push_back(track);
            return;
        }

        for(int i = start; i < digits.size(); i++)
        {
            int digit = digits[i] - '0';

            for(auto c : valToIndex[digit])
            {
                track.push_back(c);

                backtrack(digits, i + 1);

                track.pop_back();
            }
        }
    }
};


class Solution {
public:

    vector<int> memo;

    int coinChange(vector<int>& coins, int amount) 
    {
        memo = vector<int>(amount + 1, -777);

        return dp(coins, amount);
    }

    int dp(vector<int>& coins, int amount)
    {
        // base case
        if(amount == 0)
            return 0;
        if(amount < 0)
            return -1;
        
        if(memo[amount] != -777)
            return memo[amount];

        int ret = INT_MAX;
        for(auto coin : coins)
        {
            int subProblem = dp(coins, amount - coin);
            if(subProblem == -1)
                continue;

            ret = min(ret, subProblem + 1);
        }

        memo[amount] = (ret == INT_MAX) ? -1 : ret;

        return memo[amount];
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) 
    {
        int n = nums.size();

        // dp数组的定义：dp[i]表示的是以nums[i]结尾的最大子数组和
        vector<int> dp(n);

        // base case
        dp[0] = nums[0];

        int ret = INT_MIN;
        for(int i = 1; i < n; i++)
        {
            dp[i] = max(nums[i], nums[i] + dp[i-1]);
        }

        for(int i = 0; i < n; i++)
        {
            ret = max(ret, dp[i]);
        }

        return ret;
    }
};


class Solution {
public:
    bool canPartition(vector<int>& nums) 
    {
        int n = nums.size();

        int sum = 0;
        for(auto num : nums)
        {
            sum += num;
        }

        if(sum % 2 != 0)
        {
            return false;
        }

        sum /= 2;

        // dp数组的定义：dp[i][j]表示的是当背包容量为j的情况下，背包装前i个物品恰好装满
        vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1, false));

        // base case
        for(int i = 0; i <= n; i++)
        {
            dp[i][0] = true;
        }

        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= sum; j++)
            {
                // 判断当前的背包容量是否能装进第i个物品
                if(j - nums[i - 1] < 0)
                {
                    dp[i][j] = dp[i-1][j];
                }
                else
                {
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
                }
            }
        }

        return dp[n][sum];
    }
};


class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) 
    {
        int n = nums.size();

        if(n == 0)
            return 0;

        // dp函数的定义：返回nums[i..]通过在前面加上+-号可以构造一个表达式结果为target的数目
        return dp(nums, 0, target);
    }

    // DP问题中经常将状态作为key值
    unordered_map<string, int> memo;

    int dp(vector<int>& nums, int i, int remain)
    {
        // base case
        if(i == nums.size())
        {
            if(remain == 0)
                return 1;

            return 0;
        }

        string key = to_string(i) + ',' + to_string(remain);

        if(memo.count(key))
        {
            return memo[key];
        }

        int result = dp(nums, i + 1, remain - nums[i]) + dp(nums, i + 1, remain + nums[i]);

        memo[key] = result;

        return memo[key];
    }
};


class Solution {
public:
    int minInsertions(string s) 
    {
        // 解题思路，先计算出该字符串的最长回文子序列，然后字符串的长度-回文子序列的长度即是本题答案
        int n = s.size();

        // dp数组的定义：dp[i][j]表示的是s[i,j]范围内最长回文子序列的长度
        vector<vector<int>> dp(n, vector<int>(n));

        // base case
        for(int i = 0; i < n; i++)
        {
            dp[i][i] = 1;
        }

        for(int i = n - 1; i >= 0; i--)
        {
            for(int j = i + 1; j < n; j++)
            {
                if(s[i] == s[j])
                {
                    dp[i][j] = dp[i+1][j-1] + 2;
                }
                else
                {
                    dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
                }
            }
        }

        return n - dp[0][n-1];

    }
};


class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) 
    {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();

        // dp数组的定义：dp[i][j]表示的是从[0,0]到nums[i,j]的路径总数
        vector<vector<int>> dp(m, vector<int>(n, 0));

        // base case
        for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++)
        {
            dp[i][0] = 1;
        }
        for(int j = 0; j < n && obstacleGrid[0][j] == 0; j++)
        {
            dp[0][j] = 1;
        }

        for(int i = 1; i < m; i++)
        {
            for(int j = 1; j < n; j++)
            {
                if(obstacleGrid[i][j] == 1)
                {
                    continue;
                }

                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

        return dp[m-1][n-1];

    }
};


class Solution {
public:
    int maxProfit(int k, vector<int>& prices) 
    {
        int n = prices.size();

        vector<vector<vector<int>>> dp(n, vector<vector<int>>(k + 1, vector<int>(2)));

        for(int i = 0; i < n; i++)
        {
            for(int j = 1; j <= k; j++)
            {
                // base case
                if(i - 1 == -1)
                {
                    dp[i][j][0] = 0;
                    dp[i][j][1] = -prices[i];
                    continue;
                }

                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
            }
        }

        return dp[n-1][k][0];
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) 
    {
        vector<int> ret = dp(root);

        return max(ret[0], ret[1]);
    }

    vector<int> dp(TreeNode* root)
    {
        if(root == nullptr)
        {
            return {0, 0};
        }

        vector<int> left = dp(root->left);
        vector<int> right = dp(root->right);

        int rob = root->val + left[0] + right[0];
        int notRob = max(left[0], left[1]) + max(right[0], right[1]);

        return {notRob, rob};
    }
};


class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) 
    {
        // dp数组的定义：dp[i]表示的是总和为i的元素排列数
        vector<int> dp(target + 1, 0);

        // base case
        dp[0] = 1;

        for(int i = 1; i <= target; i++) // 遍历背包
        {
            for(int j = 0; j < nums.size(); j++) // 遍历物品
            {
                if(i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i-nums[j]])
                {
                    dp[i] += dp[i-nums[j]];
                }
            }
        }

        return dp[target];
    }
};


class Solution {
public:
    int bestTiming(vector<int>& prices) 
    {
        if(prices.empty())
            return 0;
        
        int n = prices.size();

        vector<vector<int>> dp(n, vector<int>(2));

        for(int i = 0; i < n; i++)
        {
            // base case
            if(i - 1 == -1)
            {
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }

            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], -prices[i]);
        }

        return dp[n-1][0];
    }
};



